package com.cat.dataStructure03;
import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/number-of-distinct-roll-sequences/
 * @create 2025/11/16 19:22
 * @since JDK17
 */

public class Solution73 {
    static int[][] g;
    static int[][][] dp;
    static int N = ((int) 1e9) + 7, mx = ((int) (1e4 + 1));
    static {
        g = new int[7][7];
        dp = new int[mx + 1][7][7];
        for (int i = 1; i < 7; i++) {
            for (int j = 1; j < 7; j++) {
                g[i][j] = gcd(i, j);
            }
        }
        for (int i = 0; i <= mx; i++) {
            for (int j = 0; j < 7; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
    }
    static int gcd(int x, int y) {
        return y == 0 ? x : gcd(y, x % y);
    }
    int dfs(int n, int last1, int last2) {
        if (n == 0) {
            return 1;
        }
        if (dp[n][last1][last2] != -1) {
            return dp[n][last1][last2];
        }
        int ans = 0;
        for (int i = 1; i < 7; i++) {
            if (i != last1 && i != last2 && g[i][last1] == 1) {
                ans = (ans + dfs(n - 1, i, last1)) % N;
            }
        }

        return dp[n][last1][last2] = ans;
    }
    public int distinctSequences(int n) {
        return dfs(n, 0, 0);
    }
}
